{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Depth of Binary Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #breadth-first-search #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #广度优先搜索 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxDepth"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #二叉树的最大深度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二叉树 <code>root</code> ，返回其最大深度。</p>\n",
    "\n",
    "<p>二叉树的 <strong>最大深度</strong> 是指从根节点到最远叶子节点的最长路径上的节点数。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/11/26/tmp-tree.jpg\" style=\"width: 400px; height: 277px;\" /></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>root = [3,9,20,null,null,15,7]\n",
    "<b>输出：</b>3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>root = [1,null,2]\n",
    "<b>输出：</b>2\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>树中节点的数量在&nbsp;<code>[0, 10<sup>4</sup>]</code>&nbsp;区间内。</li>\n",
    "\t<li><code>-100 &lt;= Node.val &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-depth-of-binary-tree](https://leetcode.cn/problems/maximum-depth-of-binary-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-depth-of-binary-tree](https://leetcode.cn/problems/maximum-depth-of-binary-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[3,9,20,null,null,15,7]', '[1,null,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        return max(self.maxDepth(root.left)+1, self.maxDepth(root.right) + 1)\n",
    "       \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if root==None:\n",
    "            return 0\n",
    "\n",
    "        stack = [root]\n",
    "        depth =1\n",
    "\n",
    "        while len(stack)>0:\n",
    "            p = stack[-1]\n",
    "            if p.left is not None:\n",
    "                stack.append(p.left)\n",
    "                depth = max(len(stack), depth)\n",
    "                p.left = None\n",
    "\n",
    "            elif p.right is not None:\n",
    "                stack.append(p.right)\n",
    "                depth = max(len(stack), depth)\n",
    "                p.right = None\n",
    "\n",
    "            else:\n",
    "                stack.pop()\n",
    "\n",
    "        return depth\n",
    "\n",
    "            \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        a = []\n",
    "        b = TreeNode(0)\n",
    "        max = 0\n",
    "        if root == None:\n",
    "            return 0\n",
    "        a.append(root)\n",
    "        while a!=[]:\n",
    "            if a[-1].left:\n",
    "                b = a[-1].left\n",
    "                a[-1].left = None\n",
    "                a.append(b)             \n",
    "            elif a[-1].right:\n",
    "                b = a[-1].right\n",
    "                a[-1].right = None\n",
    "                a.append(b)\n",
    "            else:\n",
    "                if len(a)>max:\n",
    "                    max = len(a)\n",
    "                a.pop()\n",
    "        return max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if root==None:\n",
    "            return 0\n",
    "        stack=[(root,1)]\n",
    "        dictmap={}\n",
    "        while stack:\n",
    "            root,depth=stack.pop()\n",
    "            if root.val in dictmap:\n",
    "                if dictmap[root.val]<depth:\n",
    "                    dictmap[root.val]=depth\n",
    "            else:\n",
    "                dictmap[root.val]=depth\n",
    "            if root.right:\n",
    "                stack.append((root.right,depth+1))\n",
    "            if root.left:\n",
    "                stack.append((root.left,depth+1))\n",
    "        print(dictmap)\n",
    "        return max(dictmap.values())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        query=[]\n",
    "        res=[]\n",
    "        query.append(root)\n",
    "        if root:\n",
    "            res.append(root.val)\n",
    "        else:\n",
    "            return 0\n",
    "        while query:\n",
    "            temp=query.pop(0)\n",
    "            left=temp.left\n",
    "            right=temp.right\n",
    "            if left:\n",
    "                query.append(left)\n",
    "                res.append(left.val)\n",
    "            else:\n",
    "                res.append(left)\n",
    "            if right:\n",
    "                query.append(right)\n",
    "                res.append(right.val)\n",
    "            else:\n",
    "                res.append(right)\n",
    "                \n",
    "        sign=[0,1]\n",
    "        j=0\n",
    "        while True:\n",
    "            m=0\n",
    "            for k in res[sign[j]:sign[j+1]]:\n",
    "                if k!=None:\n",
    "                    m+=1\n",
    "            j+=1\n",
    "            sign.append(sign[-1]+2*m)\n",
    "            if len(res)<=sign[-1]:\n",
    "                break\n",
    "        # sign.pop(0)\n",
    "        print('sign:',sign)\n",
    "        \n",
    "        i=0\n",
    "        s=0\n",
    "        re=[]\n",
    "        while True:\n",
    "            if len(res)>sign[i]+1:\n",
    "                re.append(res[sign[i]:sign[i+1]])\n",
    "                # print(sign[i])\n",
    "            else:\n",
    "                break\n",
    "            # s+=2**i\n",
    "            i+=1\n",
    "        \n",
    "        result=[]\n",
    "        for num in re:\n",
    "            result.append([])\n",
    "            for i in range(len(num)):\n",
    "                if num[i]!=None:\n",
    "                    result[-1].append(num[i])   \n",
    "        return len(result)-1\n",
    "        print(res)\n",
    "        print(re)\n",
    "        print(result)\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root):\n",
    "      \"\"\"\n",
    "      :type root: TreeNode\n",
    "      :rtype: int\n",
    "      \"\"\"\n",
    "      if root is None:\n",
    "        return 0\n",
    "      nodes = [root]\n",
    "      max_depth = 1\n",
    "      node_to_depth = {root: 1}\n",
    "      while nodes:\n",
    "          node = nodes.pop(0)\n",
    "          depth = node_to_depth[node]\n",
    "          left = node.left\n",
    "          right = node.right\n",
    "          depth += 1\n",
    "          if left:\n",
    "              max_depth = max(max_depth, depth)\n",
    "              node_to_depth[left] = depth\n",
    "              nodes.append(left)\n",
    "          if right:\n",
    "              max_depth = max(max_depth, depth)\n",
    "              node_to_depth[right] = depth\n",
    "              nodes.append(right)\n",
    "      return max_depth\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "import queue\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        stack = []\n",
    "        if root is not None:\n",
    "            stack.append((1,root))\n",
    "            depth = 0\n",
    "            while stack != []:\n",
    "                current_depth, root = stack.pop()\n",
    "                if root:\n",
    "                    depth = max(depth, current_depth)\n",
    "                    stack.append((current_depth + 1, root.right))\n",
    "                    stack.append((current_depth + 1, root.left))\n",
    "            return depth\n",
    "        else:\n",
    "            return 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return 0\n",
    "        else:\n",
    "            return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return 0\n",
    "        else:\n",
    "            return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if root == None:\n",
    "            return 0\n",
    "        def dfs(root):\n",
    "            if root != None:\n",
    "                return max(dfs(root.left),dfs(root.right))+1\n",
    "                \n",
    "                \n",
    "            else:\n",
    "                return 0\n",
    "            \n",
    "            \n",
    "        \n",
    "        return dfs(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return 0\n",
    "        depths = []\n",
    "        def explore(root,height,l):\n",
    "            if not root.left and not root.right:\n",
    "                l.append(height)\n",
    "                return \n",
    "            \n",
    "            if root.left:\n",
    "                explore(root.left,height+1,l)\n",
    "            \n",
    "            if root.right:\n",
    "                explore(root.right,height+1,l)\n",
    "                \n",
    "        explore(root,1,depths)\n",
    "        \n",
    "        return max(depths)\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def levelTree(root, last_level):\n",
    "            if not root:\n",
    "                return last_level\n",
    "            l = last_level + 1\n",
    "            r = last_level + 1\n",
    "            if root.left:\n",
    "                l = levelTree(root.left, last_level + 1)\n",
    "            if root.right:\n",
    "                r = levelTree(root.right, last_level + 1)\n",
    "            return max(l, r)\n",
    "\n",
    "        return levelTree(root, 0)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        \n",
    "        def height(node):\n",
    "            if not node:\n",
    "                return 0\n",
    "            left = height(node.left)\n",
    "            right =height(node.right)\n",
    "            return max(left,right)+1\n",
    "        \n",
    "        return height(root)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not root:\n",
    "            return 0\n",
    "        return 1 + max(map(self.maxDepth,(root.left,root.right)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "\n",
    "        def dfs(root):\n",
    "            if root == None:\n",
    "                return 0\n",
    "            else:\n",
    "                print(root.val)\n",
    "                l = dfs(root.left) + 1\n",
    "                r = dfs(root.right) + 1 \n",
    "                return max(l, r)\n",
    "        \n",
    "    \n",
    "        return dfs(root)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        return 1+max(map(self.maxDepth,(root.left,root.right))) if root else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        count = 0\n",
    "        stack = [root]\n",
    "        while stack:\n",
    "            count += 1\n",
    "            tempstack = []  # 装下一层节点\n",
    "            for root in stack:\n",
    "                if root.left:\n",
    "                    tempstack.append(root.left)\n",
    "                if root.right:\n",
    "                    tempstack.append(root.right)\n",
    "            stack = tempstack\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        stack = []\n",
    "        if root is not None:\n",
    "            stack.append(root)\n",
    "        \n",
    "        depth = 0\n",
    "        while stack != []:\n",
    "\n",
    "            depth += 1\n",
    "            for i in range(len(stack)):\n",
    "                root = stack.pop(0)\n",
    "                if root.left != None:\n",
    "                    stack.append(root.left)\n",
    "                if root.right != None:\n",
    "                    stack.append(root.right)\n",
    "        \n",
    "        return depth\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    # sol 1: Recursion\n",
    "    def maxDepth_v1(self, root: TreeNode) -> int:\n",
    "        def helper(root: TreeNode, level: int) -> int:\n",
    "            if not root:\n",
    "                return level - 1\n",
    "            \n",
    "            return max(helper(root.left, level + 1), helper(root.right, level + 1))\n",
    "        \n",
    "        return helper(root, 1)\n",
    "\n",
    "    \n",
    "    # sol 2: Level-order-travesarl.\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        from collections import deque\n",
    "        if not root:\n",
    "            return 0\n",
    "        q = deque([root])\n",
    "        level = 0\n",
    "        while q:\n",
    "            level += 1\n",
    "            prev_level_size = len(q)\n",
    "            for _ in range(prev_level_size):\n",
    "                node = q.popleft()\n",
    "                if node.left:\n",
    "                    q.append(node.left)\n",
    "                if node.right:\n",
    "                    q.append(node.right)\n",
    "        \n",
    "        return level"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        queue = collections.deque()\n",
    "        queue.append(root)\n",
    "        ans = 0\n",
    "        while queue:\n",
    "            ans+=1\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        depth = 0\n",
    "        stack = []\n",
    "        stack.append(root)\n",
    "\n",
    "        while stack:\n",
    "            length = len(stack)\n",
    "            for _ in range(length):\n",
    "                root = stack.pop(0)\n",
    "                if root.left:\n",
    "                    stack.append(root.left)\n",
    "                if root.right:\n",
    "                    stack.append(root.right)\n",
    "\n",
    "            depth += 1\n",
    "\n",
    "        return depth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        depth = 0\n",
    "        node = root\n",
    "        my_queue = []\n",
    "        my_queue.append(node)\n",
    "\n",
    "        while my_queue:\n",
    "            count = len(my_queue)\n",
    "            depth = depth + 1\n",
    "            while count > 0:\n",
    "                node = my_queue.pop(0)\n",
    "                if node.left is not None:\n",
    "                    my_queue.append(node.left)\n",
    "                if node.right is not None:\n",
    "                    my_queue.append(node.right)\n",
    "                count -= 1\n",
    "\n",
    "        return depth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        nodes = [root]\n",
    "        res = []\n",
    "        while len(nodes) > 0:\n",
    "            n = len(nodes)\n",
    "            for node in nodes[:]:\n",
    "                if node.left:\n",
    "                    nodes.append(node.left)\n",
    "                if node.right:\n",
    "                    nodes.append(node.right)\n",
    "            p, nodes = nodes[:n], nodes[n:]\n",
    "            res.append([i.val for i in p])\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        '''递归，后序遍历（DFS）\n",
    "        if not root:\n",
    "            return 0\n",
    "        return max(self.maxDepth(root.left),self.maxDepth(root.right))+1\n",
    "        '''\n",
    "        if not root:\n",
    "            return 0\n",
    "        \n",
    "        queue,res=[root],0\n",
    "        while queue:\n",
    "            tem = []\n",
    "            for i in queue:\n",
    "                if i.left:\n",
    "                    tem.append(i.left)\n",
    "                if i.right:\n",
    "                    tem.append(i.right)\n",
    "            queue = tem \n",
    "            res += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        else:\n",
    "            return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        if not root.left and not root.right:\n",
    "            return 1\n",
    "\n",
    "        l = self.maxDepth(root.left)\n",
    "        r = self.maxDepth(root.right)\n",
    "\n",
    "        return max(l, r) + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        depth_v = 0\n",
    "        if root is None:\n",
    "            return depth_v\n",
    "        node_list = [root]\n",
    "        while(True):\n",
    "            if len(node_list) == 0:\n",
    "                return depth_v\n",
    "            depth_v += 1\n",
    "            new_node_list = []\n",
    "            for item in node_list:\n",
    "                if item.left is not None:\n",
    "                    new_node_list.append(item.left)\n",
    "                if item.right is not None:\n",
    "                    new_node_list.append(item.right)\n",
    "            node_list = new_node_list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root :\n",
    "            return 0\n",
    "        queue = deque([root])\n",
    "        height = 0\n",
    "        while queue:\n",
    "            currentsize=len(queue)\n",
    "            for i in range(currentsize):\n",
    "                node=queue.popleft()\n",
    "                if node.left!=None:\n",
    "                    queue.append(node.left)\n",
    "                if node.right!=None:\n",
    "                    queue.append(node.right)\n",
    "            height+=1\n",
    "        return height"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: TreeNode) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        queue = collections.deque([root])\n",
    "        depth = 0\n",
    "        while queue:\n",
    "            depth += 1\n",
    "            for _ in range(len(queue)):\n",
    "                node = queue.popleft()\n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "                # 将不再需要使用的节点从内存中删除\n",
    "                node.left = None\n",
    "                node.right = None\n",
    "        return depth\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if root == None:\n",
    "            return 0\n",
    "\n",
    "        queue_ = [root]\n",
    "        depth = 0\n",
    "        while queue_:\n",
    "            length = len(queue_)\n",
    "            for i in range(length):\n",
    "                cur = queue_.pop(0)\n",
    "                #子节点入队列\n",
    "                if cur.left: queue_.append(cur.left)\n",
    "                if cur.right: queue_.append(cur.right)\n",
    "            depth += 1\n",
    "\n",
    "        return depth"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        deep = 0\n",
    "        if root==None:\n",
    "            return deep\n",
    "        from collections import deque\n",
    "        queue = deque([root])\n",
    "        while queue:\n",
    "            deep +=1\n",
    "            size = len(queue)\n",
    "            for i in range(size):\n",
    "                cur = queue.popleft()\n",
    "                if cur.left:\n",
    "                    queue.append(cur.left)\n",
    "                if cur.right:\n",
    "                    queue.append(cur.right)\n",
    "        return deep\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        res=0\n",
    "        stack=[[root,1]]\n",
    "        while stack:\n",
    "            node,depth=stack.pop()\n",
    "            if node:\n",
    "                res=max(res,depth)\n",
    "                stack.append([node.left,depth+1])\n",
    "                stack.append([node.right,depth+1])\n",
    "        return res\n",
    "       \n",
    "\n",
    "       "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        queue = collections.deque([root])\n",
    "        distance = {root: 1}\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            if node.left:\n",
    "                queue.append(node.left)\n",
    "                distance[node.left] = distance[node] + 1\n",
    "            if node.right:\n",
    "                queue.append(node.right)\n",
    "                distance[node.right] = distance[node] + 1\n",
    "        return  distance[max(distance, key=distance.get)]    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if root == None:\n",
    "            return 0\n",
    "        result = []\n",
    "        q = deque([root])\n",
    "        while q:\n",
    "            vals = []\n",
    "            for _ in range(len(q)):\n",
    "                node = q.popleft()\n",
    "                vals.append(node.val)\n",
    "                if node.left: q.append(node.left)\n",
    "                if node.right: q.append(node.right)\n",
    "            result.append(vals)\n",
    "        return len(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        # DFS\n",
    "        # if root:\n",
    "        #     return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))\n",
    "        # else:\n",
    "        #     return 0\n",
    "\n",
    "        # BFS\n",
    "        # queue = collections.deque()\n",
    "        # if root: \n",
    "        #     queue.append(root)\n",
    "        # depth = 0\n",
    "        # while queue:\n",
    "        #     n = len(queue)\n",
    "        #     while n > 0:\n",
    "        #         node = queue.popleft()\n",
    "        #         if node.left:\n",
    "        #             queue.append(node.left)\n",
    "        #         if node.right:\n",
    "        #             queue.append(node.right)\n",
    "        #         n -= 1\n",
    "        #     depth += 1\n",
    "        # return depth\n",
    "\n",
    "        # Stack\n",
    "        maxDepth = 0\n",
    "        if not root: return 0\n",
    "        stk = [(root,1)]\n",
    "        while stk:\n",
    "            node, depth = stk.pop()\n",
    "            maxDepth = max(maxDepth, depth)\n",
    "            if node.left:\n",
    "                stk.append((node.left, depth + 1))\n",
    "            if node.right:\n",
    "                stk.append((node.right, depth + 1))\n",
    "        return maxDepth\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        res = 0\n",
    "        if not root:\n",
    "            return res\n",
    "        queue = [root]\n",
    "        while queue:\n",
    "            level = []\n",
    "            for node in queue:\n",
    "                if node.left:\n",
    "                    level.append(node.left)\n",
    "                if node.right:\n",
    "                    level.append(node.right)\n",
    "            res += 1\n",
    "            queue = level\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        result=[]\n",
    "        queue = collections.deque([root])\n",
    "        \n",
    "        while queue:\n",
    "            level_size = len(queue)\n",
    "            #prev = None\n",
    "            level=[]\n",
    "            for i in range(level_size):\n",
    "                node = queue.popleft()\n",
    "                \n",
    "                # if prev:\n",
    "                #     prev.next = node\n",
    "                \n",
    "                # prev = node\n",
    "                \n",
    "                if node.left:\n",
    "                    queue.append(node.left)\n",
    "                \n",
    "                if node.right:\n",
    "                    queue.append(node.right)\n",
    "                level.append(node)\n",
    "            result.append(level)\n",
    "        ans=len(result)\n",
    "        return ans     "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if not root:\n",
    "            return 0\n",
    "        else:\n",
    "            return 1 + max(self.maxDepth(root.right), self.maxDepth(root.left))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: Optional[TreeNode]) -> int:\n",
    "        if root is None:\n",
    "            return 0\n",
    "        l_depth=self.maxDepth(root.left)\n",
    "        r_depth=self.maxDepth(root.right)\n",
    "        return max(l_depth,r_depth) + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def maxDepth(self, root: Optional[TreeNode]) -> int:\n",
    "\n",
    "        if root is None:\n",
    "            return 0\n",
    "        md = 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))\n",
    "        return md\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
